//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
// Related Topics 栈 数组 单调栈 👍 1913 👎 0

package leetcode.editor.cn;

import java.util.Stack;

class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 动态规划
         *
         * @param heights
         * @return
         */
//        public int largestRectangleArea(int[] heights) {
//            int[] minLeftIndex = new int[heights.length];
//            int[] minRightIndex = new int[heights.length];
//            int maxSize = 0;
//
//            // 记录每个柱子 左边第一个小于该柱子的下标
//            minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
//            for (int i = 1; i < heights.length; i++) {
//                int t = i - 1;
//                // 这里不是用if，而是不断向左寻找的过程
//                while (t >= 0 && heights[t] >= heights[i])
//                    t = minLeftIndex[t];    // while一直循环找到左边第一个小于该柱子的下标
//                minLeftIndex[i] = t;
//            }
//
//            minRightIndex[heights.length - 1] = heights.length;
//            for (int i = heights.length - 2; i >= 0; i--) {
//                int t = i + 1;
//                // 这里不是用if，而是不断向左寻找的过程
//                while (t < heights.length && heights[t] >= heights[i])
//                    t = minRightIndex[t];      // 记录每个柱子 右边第一个小于该柱子的下标
//                minRightIndex[i] = t;
//            }
//
//            // 求和
//            for (int i = 0; i < heights.length; i++) {
//                int size = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
//                if (size > maxSize) maxSize = size;
//            }
//
//            return maxSize;
//        }
        public int largestRectangleArea(int[] heights) {
            // 数组扩容，在头尾各加一个元素
            int[] array = new int[heights.length + 2];
            array[0] = 0;
            array[heights.length + 1] = 0;
            for (int i = 0; i < heights.length; i++) {
                array[i + 1] = heights[i];
            }
            Stack<Integer> stack = new Stack<>();
            stack.push(0);  // 栈顶到栈底，从大到小
            int maxSize = 0;

            heights = array;    // 需要在头尾各加一个0，来保证大小为2或者1时特殊情况，和都是相同的数字也是特殊情况
            for (int i = 1; i < heights.length; i++) {
                if (heights[stack.peek()] < heights[i]) {
                    stack.push(i);
                } else if (heights[stack.peek()] == heights[i]) {
                    stack.pop();
                    stack.push(i);
                } else {
                    while (heights[stack.peek()] > heights[i]) {
                        Integer mid = stack.peek();
                        stack.pop();
                        Integer left = stack.peek();
                        int size = (i - left - 1) * heights[mid];
                        maxSize = Math.max(size, maxSize);
                    }
                    stack.push(i);
                }
            }

            return maxSize;
        }

        /**
         * 双指针法(超时)
         *
         * @param heights
         * @return
         */
        /*public int largestRectangleArea(int[] heights) {
            int maxSize = 0;
            for (int i = 0; i < heights.length; i++) {
                int leftIndex = i;
                int rightIndex = i;

                // 找到小于i的高度
                for (; leftIndex >= 0; leftIndex--) {
                    if (heights[leftIndex] < heights[i]) break;
                }

                for (; rightIndex < heights.length; rightIndex++) {
                    if (heights[rightIndex] < heights[i]) break;
                }

                int high = heights[i];
                int width = rightIndex - leftIndex - 1;
                maxSize = Math.max(maxSize, high * width);
            }
            return maxSize;
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
